package simple;

import java.util.Arrays;

/**
 * 题目:
 * 描述
 * 给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组
 * 注意：
 * 1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n
 * 2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了
 * 3. A 数组在[0,m-1]的范围也是有序的
 * 示例1
 * 输入：
 * [4,5,6],[1,2,3]
 * 复制
 * 返回值：
 * [1,2,3,4,5,6]
 * 复制
 * 说明：
 * A数组为[4,5,6]，B数组为[1,2,3]，后台程序会预先将A扩容为[4,5,6,0,0,0]，B还是为[1,2,3]，m=3，n=3，传入到函数merge里面，然后请同学完成merge函数，将B的数据合并A里面，最后后台程序输出A数组
 *
 *
 * @author WangZhiJian
 * @since 2021/12/31
 */
public class 合并两个有序的数组 {
    /**
     * 解题说明:
     *  由于是有序数组从小排序到大,可以先把A数组的所有数字都移动到A数组后端,再执行排序
     *  也可以换个思路,从大排序到小,逆向排序,
     *  下方代码即是逆向排序
     * @param A
     * @param m
     * @param B
     * @param n
     */
    public static void merge(int A[], int m, int B[], int n) {
        int len = m+n - 1;
        int i = m -1;
        int j = n - 1;
        while(i >= 0 && j >= 0) {
            A[len --] = A[i] > B[j] ? A[i --] : B[j --];
        }
        while (j >= 0)
            A[len --] = B[j --];
    }

    public static void main(String[] args) {
        int[] res = new int[]{4,5,6,0,0,0};
        merge(res,3,new int[]{1,2,3},3);
        System.out.println(Arrays.toString(res));
    }
}
